package com.wfm.leetcode.editor.cn;

import java.util.TreeMap;

/**
 * 左边用minLeft维持个最小值
 * 右边用hashtree对所有元素排序
 * 遍历中间的j
 * O(nlogn) 加入有序集合O(nlogn)、遍历j要O(n)、从有序集合删除元素要O(logn);
 * O(n) 有序集合使用的空间
 */
public class PFour56One32模式{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean find132pattern(int[] nums) {
        // 小于三位数直接返回
        int n = nums.length;
        if(n<3) return false;

        // 最侧最小
        int leftMin = nums[0];

        // 右侧所有
        TreeMap<Integer,Integer> rightAll = new TreeMap<>();
        for (int k = 2; k < n; k++) {
            rightAll.put(nums[k],rightAll.getOrDefault(nums[k],0)+1);
        }
        for (int j = 1; j < n-1; j++) {
            if (leftMin < nums[j]) {
                Integer next = rightAll.ceilingKey(leftMin + 1);
                if (next != null && next < nums[j]) {
                    return true;
                }
            }
            leftMin = Math.min(leftMin, nums[j]);
            rightAll.put(nums[j + 1], rightAll.get(nums[j + 1]) - 1);
            if (rightAll.get(nums[j + 1]) == 0) {
                rightAll.remove(nums[j + 1]);
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour56One32模式().new Solution();
    }
}